package com.goudan.practice.tree;

/**
 * 搜索二叉树判断
 * - 题目：如何判断一颗二叉树是搜索二叉树？
 * - 搜索二叉树的特点：任何一个节点，左子树的节点一定比它小，右子树的节点一定比它大
 * - 解题： 中序遍历一定是升序，如果某个位置有降序，一定不是搜索二叉树
 */
public class CheckSearchTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static void main(String[] args) {

    }

    //--------------------解法1：递归解法：中序遍历判断---------------------
    public static int preValue = Integer.MIN_VALUE;

    /**
     * 递归解法：中序遍历判断
     */
    public static boolean checkBST(Node head) {
        if (head == null) {
            return true;
        }
        boolean checkLeft = checkBST(head.left);
        if (!checkLeft) {
            return false;
        }
        if (head.value <= preValue) {
            return false;
        } else {
            preValue = head.value;
        }
        return checkBST(head.right);
    }
    //--------------------解法1：递归解法：中序遍历判断---------------------

    //--------------------解法2：递归解法：递归套路---------------------

    /**
     * 递归返回值
     */
    public static class Info {
        public boolean isBST; // 是否是搜索二叉树
        public int max; // 最大值
        public int min; // 最小值

        public Info(boolean i, int ma, int mi) {
            isBST = i;
            max = ma;
            min = mi;
        }
    }

    public static Info process(Node x) {
        if (x == null) {
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int min = x.value;
        int max = x.value;
        // 最小值和最大值就是我当前节点的值和它比较得出的最小值和最大值
        if (leftInfo != null) {
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
        }
        if (rightInfo != null) {
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
        }
        // 是否是搜索二叉树
        boolean isBST = true;
        // 左边有信息并且左边不是搜索二叉树
        if (leftInfo != null && !leftInfo.isBST) {
            isBST = false;
        }
        if (rightInfo != null && !rightInfo.isBST) {
            isBST = false;
        }
        // 左边有信息，但是左边的最大值大于等于我的值
        if (leftInfo != null && leftInfo.max >= x.value) {
            isBST = false;
        }
        // 右边有信息，右边的最小值小于等于我当前值
        if (rightInfo != null && rightInfo.min <= x.value) {
            isBST = false;
        }
        return new Info(isBST, max, min);
    }

    public static boolean otherIsBST(Info leftInfo, Info rightInfo, Node x) {
        // 默认不是搜索二叉树
        boolean isBST = false;
        if (
                (leftInfo != null ? (leftInfo.isBST && leftInfo.max < x.value) : true) &&
                        (rightInfo != null) ? (rightInfo.isBST && rightInfo.min > x.value) : true
        ) {
            isBST = true;
        }
        return isBST;
    }
    //--------------------解法2：递归解法：递归套路---------------------

}
